#include <iostream>
using namespace std;

const int N = 1e6 + 10;

int l[N],r[N];

void dfsx(int p){
	cout << p << " ";
	if(l[p]) dfsx(l[p]);
	if(r[p]) dfsx(r[p]);
}

void dfsz(int p){
	if(l[p]) dfsz(l[p]);
	cout << p << " ";
	if(r[p]) dfsz(r[p]);
}

void dfsh(int p){
	if(l[p]) dfsh(l[p]);
	if(r[p]) dfsh(r[p]);
	cout << p << " ";
}

int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n;i++){
		cin >> l[i] >> r[i];
	}
	dfsx(1);
	cout << endl;
	dfsz(1);
	cout << endl;
	dfsh(1);
	cout << endl;
	return 0;
} 
